package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/">497. 非重叠矩形中的随机点</a>
 * <p>
 * tags: 概率; 抽样
 */
public class Problem497 {
    private static class Solution {
        private final int[][] rects;
        Random random = new Random();
        int[] bounds;
        int pointCount;

        public Solution(int[][] rects) {
            this.rects = rects;
            int pointCount = 0;
            List<Integer> bounds = new ArrayList<>();
            bounds.add(0);
            for (int[] rect : rects) {
                int rectPointCount = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
                pointCount += rectPointCount;
                bounds.add(pointCount);
            }
            this.pointCount = pointCount;
            this.bounds = bounds.stream().mapToInt(i -> i).toArray();
        }

        public int[] pick() {
            int index = random.nextInt(1, pointCount + 1);
            int rectI = binarySearch(bounds, index) - 1;
            int offset = index - 1 - bounds[rectI];
            int width = rects[rectI][2] - rects[rectI][0] + 1;
            int x = rects[rectI][0] + offset % width;
            int y = rects[rectI][1] + offset / width;
            return new int[]{x, y};
        }

        public int binarySearch(int[] space, int target) {
            int left = 0;
            int right = space.length - 1;
            while (left <= right) {
                int mid = left + (right - left >> 1);
                if (target == space[mid]) {
                    return mid;
                } else if (target > space[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution(new int[][]{{-2, -2, 1, 1}, {2, 2, 4, 6}});
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
    }
}
